// Time:  O(n)
// Space: O(1)

#include <vector>

using namespace std;

class Solution
{
public:
    vector<vector<int>> insert(vector<vector<int>> &intervals, vector<int> &newInterval)
    {
        int n = intervals.size(), i = 0;
        vector<vector<int>> result;
        // case 1: no overlapping case before the merge interval
        // compare ending point of intervals to starting point of newInterval
        while (i < n && intervals[i][1] < newInterval[0])
        {
            result.push_back(intervals[i]);
            ++i;
        }

        // case 2: overlapping case
        // merge the overlapping intervals
        while (i < n && newInterval[1] >= intervals[i][0])
        {
            newInterval[0] = min(newInterval[0], intervals[i][0]);
            newInterval[1] = max(newInterval[1], intervals[i][1]);
            ++i;
        }
        result.push_back(newInterval);

        // case 3: no overlapping of intervals after newinterval being merged
        while (i < n)
        {
            result.push_back(intervals[i]);
            ++i;
        }
        return result;
    }
};
